package com.leetcode.题库;

import com.leetcode.common.model.TreeNode;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-04-14 20:23
 */
public class 题库_0297_二叉树的序列化与反序列化 {

  static
  public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
      List<Integer> answers = new ArrayList<>();
      serialize(root, answers);
      int lastIndex = answers.size() - 1;
      while (lastIndex >= 0 && answers.get(lastIndex) == null) {
        --lastIndex;
      }
      if (lastIndex < 0) {
        return "";
      }
      String[] elements = new String[lastIndex + 1];
      for (int i = 0; i <= lastIndex; ++i) {
        elements[i] = String.valueOf(answers.get(i));
      }
      return String.join(",", elements);
    }

    private void serialize(TreeNode root, List<Integer> answers) {
      if (root == null) {
        answers.add(null);
        return;
      }
      answers.add(root.val);
      serialize(root.left, answers);
      serialize(root.right, answers);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
      if (data == null || data.length() == 0) {
        return null;
      }
      String[] splits = data.split(",");
      Deque<Integer> queue = new LinkedList<>();
      for (String num : splits) {
        if ("null".equals(num)) {
          queue.add(null);
        } else {
          queue.add(Integer.parseInt(num));
        }
      }
      return deserialize(queue);
    }

    private TreeNode deserialize(Deque<Integer> queue) {
      if (queue.isEmpty()) {
        return null;
      }
      Integer value = queue.remove();
      if (value == null) {
        return null;
      }
      TreeNode root = new TreeNode(value);
      root.left = deserialize(queue);
      root.right = deserialize(queue);
      return root;
    }
  }

}
